// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 5：
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
//
//        你可以按 任何顺序 返回答案。
//
//        示例 1：
//
//        输入：n = 4, k = 2
//        输出：
//        [
//        [2,4],
//        [3,4],
//        [2,3],
//        [1,2],
//        [1,3],
//        [1,4],
//        ]
//        示例 2：
//
//        输入：n = 1, k = 1
//        输出：[[1]]
//
//
//        提示：
//
//        1 <= n <= 20
//        1 <= k <= n

// 解题思路：
// 每一层都有 n 个选择，使用循环的方式进行选择，每次选一个，选 pos 位置的元素
// 下次选 pos + 1 的位置
// 当选取的元素个数等于 k 时，收集结果

import java.util.ArrayList;
import java.util.List;

public class Combine {
    List<List<Integer>> ret;
    List<Integer> path;
    int num;
    int kk;
    public List<List<Integer>> combine(int n, int k) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        num = n;
        kk = k;
        dfs(1);
        return ret;
    }
    public void dfs(int pos){
        if(path.size() == kk){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = pos; i <= num; i++){
            path.add(i);
            dfs(i + 1);
            path.remove(path.size() - 1);
        }
    }
}
